var AStar = {
    init: function(grid) {
		grid.each(function(x, column) {
			column.each(function(y, node) {
				node.f = 0;
				node.g = 0;
				node.h = 0;
				node.parent = null;
			});
		});
    },
    search: function(grid, start, end) {
        AStar.init(grid);
        
        var openList = [];
        var closedList = [];
        openList.push(start);
        
        while(openList.length > 0) {
        
        	// Grab the lowest f(x) to process next
            var lowInd = 0;
            for(var i=0; i<openList.length; i++) {
			    if(openList[i].f < openList[lowInd].f) { lowInd = i; }
		    }
		    var currentNode = openList[lowInd];
		    
		    // End case -- result has been found, return the traced path
		    if(currentNode == end) {
			    var curr = currentNode;
			    var ret = [];
			    while(curr.parent) {
				    ret.push(curr);
				    curr = curr.parent;
			    }
			    return ret.reverse();
		    }
    		
		    // Normal case -- move currentNode from open to closed, process each of its neighbors
		    openList.remove(currentNode);
		    closedList.push(currentNode);
		    var neighbors = AStar.neighbors(grid, currentNode);
    		
		    for(var i=0; i<neighbors.length;i++) {
			    var neighbor = neighbors[i];
			    if(closedList.find(neighbor)) {
				    // not a valid node to process, skip to next neighbor
				    continue;
			    }
    			
			    // g score is the shortest distance from start to current node, we need to check if
			    //   the path we have arrived at this neighbor is the shortest one we have seen yet
			    var gScore = currentNode.g + 1; // 1 is the distance from a node to it's neighbor
			    var gScoreIsBest = false;
    			
    			
			    if(!openList.find(neighbor)) {
				    // This the the first time we have arrived at this node, it must be the best
				    // Also, we need to take the h (heuristic) score since we haven't done so yet
    				
				    gScoreIsBest = true;
				    neighbor.h = AStar.heuristic(neighbor, end);
				    openList.push(neighbor);
			    }
			    else if(gScore < neighbor.g) {
				    // We have already seen the node, but last time it had a worse g (distance from start)
				    gScoreIsBest = true;
			    }
    			
			    if(gScoreIsBest) {
				    // Found an optimal (so far) path to this node.  Store info on how we got here and
				    //  just how good it really is...
				    neighbor.parent = currentNode;
				    neighbor.g = gScore;
				    neighbor.f = neighbor.g + neighbor.h;
				}
		    }
        }
        
        // No result was found -- empty array signifies failure to find path
        return [];
    },
    heuristic: function(pos0, pos1) {
    	// This is the Manhattan distance
        var d1 = Math.abs (pos1.x - pos0.x);
        var d2 = Math.abs (pos1.y - pos0.y);
        return d1 + d2;
    },
    neighbors: function(grid, node) {
        var ret = [];
	    var x = node.x;
	    var y = node.y;
    	
	    if(grid[x-1] && grid[x-1][y]) {
		    ret.push(grid[x-1][y]);
	    }
	    if(grid[x-1] && grid[x-1][y-1]) {
		    ret.push(grid[x-1][y-1]);
	    }
	    if(grid[x-1] && grid[x-1][y+1]) {
		    ret.push(grid[x-1][y+1]);
	    }
	    if(grid[x-1] && grid[x-1][y]) {
		    ret.push(grid[x-1][y]);
	    }
	    if(grid[x+1] && grid[x+1][y]) {
		    ret.push(grid[x+1][y]);
	    }
	    if(grid[x+1] && grid[x+1][y-1]) {
		    ret.push(grid[x+1][y-1]);
	    }
	    if(grid[x+1] && grid[x+1][y+1]) {
		    ret.push(grid[x+1][y+1]);
	    }
	    if(grid[x][y-1] && grid[x][y-1]) {
		    ret.push(grid[x][y-1]);
	    }
	    if(grid[x][y+1] && grid[x][y+1]) {
		    ret.push(grid[x][y+1]);
	    }
	    return ret;
    }
};

Array.prototype.each = function(f) {
    for(var index in this) {
    	var item = this[index];
    	if(item != Array.prototype.each && item != Array.prototype.find && item != Array.prototype.remove) {
    		f(index, this[index]); 
    	}
    }
};

Array.prototype.find = function(obj) {
	for(var i=0;i<this.length;i++) {
		if(this[i] == obj) { return this[i]; }
	}
	return false;
};

Array.prototype.remove = function(obj) {
	this.splice(this.indexOf(obj), 1);
	return false;
};